n=1000;
q=1000;
index=[261,361,425,446,510,533,636,655,827,838,961,1097,1159,1204,1417,1528,1575,1652,1768,1810,1820,1843,1862,1874,1964,2137,2214,2331,2343,2345,2420,2475,2646,2651,2655,2854,2917,3017,3026,3082,3202,3258,3286,3450,3483,3595,3730,3847,3848,3896,4042,4056,4094,4105,4150,4189,4212,4305,4356,4372,4523,4537,4541,4610,4657,4687,4696,4734,4959,4997,4999,5149,5159,5176,5240,5258,5283,5288,5306,5351,5366,5383,5420,5663,5706,5722,5742,5788,5934,5957,6124,6223,6230,6261,6334,6353,6375,6388,6588,6718,6724,6729,6733,6808,6859,6897,7008,7090,7182,7369,7443,7452,7465,7511,7522,7572,7600,7625,7631,7787,7881,7895,7896,7930,7951,7961,8223,8309,8382,8450,8509,8512,8662,8815,8834,8855,8865,8902,8916,8960,9221,9278,9319,9362,9521,9611,9631,9664,9707,9786,9910,10081,10092,10129,10195,10233,10236,10676,10700,10761,10762,10914,10968,10994,10998,11119,11125,11136,11138,11242,11258,11412,11452,11525,11608,11780,11984,12053,12068,12214,12231,12375,12395,12433,12444,12505,12593,12614,12615,12673,12715,12803,12884,12927,12940,12999,13001,13049,13069,13082,13250,13277,13385,13475,13486,13547,13792,13798,13821,13822,13846,13860,13874,13929,13976,14047,14052,14151,14212,14216,14250,14303,14316,14366,14415,14434,14454,14533,14827,14852,14932,14967,14988,15053,15065,15129,15240,15273,15274,15338,15353,15365,15437,15444,15689,15733,15776,15872,15939,15950,15983,16062,16209,16213,16214,16291,16355,16377,16390,16454,16476,16482,16612,16673,16737,16738,16773,16854,16891,16895,16941,16978,17029,17150,17209,17240,17249,17329,17348,17450,17457,17576,17633,17684,17710,17717,17775,17795,17828,17838,17913,17918,17925,17944,17980,18020,18031,18293,18377,18516,18518,18600,18614,18693,18914,18995,19069,19070,19171,19198,19198,19252,19340,19350,19384,19485,19495,19578,19615,19680,19700,19800,19801,19840,19884,20031,20056,20068,20073,20106,20147,20154,20186,20241,20248,20333,20357,20382,20451,20509,20566,20566,20573,20573,20602,20666,20674,20691,20697,20737,20755,20845,20899,20941,21067,21121,21160,21217,21254,21271,21341,21345,21361,21470,21545,21770,21790,21816,21873,21890,21900,21921,21930,21947,21978,22198,22245,22246,22257,22267,22339,22391,22461,22500,22574,22621,22683,22714,22852,22853,22921,22935,23014,23121,23344,23393,23413,23470,23539,23542,23566,23686,23780,23874,23889,23978,23989,24138,24183,24389,24467,24470,24539,24670,24688,24741,24791,24824,24916,24921,24932,24982,25058,25123,25129,25139,25186,25453,25503,25680,25692,25715,25717,25799,25828,25928,25993,25996,26009,26093,26127,26187,26208,26243,26357,26610,26654,26656,26760,26776,26790,26909,27005,27021,27051,27098,27177,27182,27243,27310,27468,27472,27483,27656,27793,27865,27923,27962,28227,28264,28285,28347,28417,28419,28458,28482,28627,28672,28685,28707,28709,28737,28790,28821,28867,28975,29056,29071,29100,29119,29173,29201,29395,29410,29421,29505,29544,29556,29574,29575,29609,29655,29855,29893,29929,29934,29946,29953,29995,30073,30199,30242,30250,30316,30333,30341,30348,30448,30507,30510,30556,30577,30586,30657,30690,30713,30729,30749,30866,30910,30948,30980,31021,31091,31097,31150,31240,31261,31302,31302,31372,31588,31622,31720,31736,31768,31797,31797,31803,31830,32033,32064,32185,32370,32408,32431,32548,32563,32566,32571,32636,32694,32772,32783,32879,32887,32915,33033,33162,33249,33284,33506,33657,34081,34224,34627,35199,35572,35621,35753,35839,35891,36604,36653,36727,37387,37607,37632,37811,38067,38123,38246,38334,38663,38846,38953,39203,39278,39835,39897,40791,41196,41271,41955,42018,42567,43729,45170,45187,45461,45709,47571,47873,48123,48332,48591,48968,49661,49842,49865,50736,51076,51132,51469,52231,53044,53709,55497,57147,57506,57593,58005,58372,58626,59966,60336,60817,61636,61735,61982,63457,63568,66626,67499,67812,68991,69322,69579,69977,70613,70949,71457,71842,71851,72028,72084,72583,73369,75956,77527,78180,78247,78433,80218,80303,80421,80817,81740,81754,81775,83723,84026,84737,86341,87063,87650,88781,89104,89464,89912,90033,90126,90944,90971,92084,92097,92107,94098,94172,94362,95294,95512,95881,96407,96964,97183,97933,98713,99272,99281,99565,99833,101447,102128,102350,102537,102837,103088,103475,104631,105089,105458,106201,106214,106383,108646,108789,109617,109907,110140,110295,110529,111762,112083,112774,112803,113042,113228,114834,116305,116440,116958,117011,117725,117893,119247,119373,119754,120275,121140,121141,122764,122871,127902,128276,128408,133647,142362,143624,144483,150162,151702,153230,153995,154474,169071,179468,189242,204946,205350,207820,219257,241380,243268,254464,256256,267800,271615,286453,295766,298139,298600,302025,303924,319539,323849,331054,331103,334245,343584,360709,361105,377771,379415,387903,404713,408905,410545,414843,427721,439756,454160,455463,456714,468519,469844,470751,476792,479652,485397,486172,488383,489118,491204,493300,498522,500974,506337,517317,519643,519878,523194,540520,546878,551123,551864,556278,578761,589849,596943,597043,607205,614085,615730,618747,638763,639794,640385,646296,658868,662096,668960,676387,683240,691160,691462,702513,711334,719636,733907,735919,736155,741705,742702,753646,755148,756375,772108,773633,782728,787005,792320,797858,812223,819109,820394,823280,830639,837193,850755,864660,868191,869777,871112,890756,916358,916675,928571,930779,942351,946404,953297,958499,967720,982578,982674,985260,988504,992066,994275,1007083,1010019,1013753,1083792,1250807,1288825,1300763,1415399,1431004,1460630,1573681,1622040,2016952,2048070,2121403,2154330,2163412,2194572,2209304,2211491,2220513,2326204,2413175,2498447,2555124,2573968,2728455,2758002,2821969,2834635,2839567,2866984,2894024,2913893,3073018,3087321,3108053,3149243,3238115,3272276,3295650,3375556,3432532,3484411,3538259,3554423,3703935,3719317,3802220,3848381,3978260,4005585,4098386,4156656,4240562,4294241,4359406,4389031,4394456,4401353,4416547,4425794,4489634,4655825,4696131,4789019,4916106,5230127,5271676,5313021,5351511,5354426,5412719,5507997,5754241,5809266,6068539,6630640,6687428,6885544,6956023,7007638,7015997,7100504,7143403,7182281,7194404,7301962,7358028,7439770,7618794,7729881,7746153,8263762,8287243,8390532,8432339,8443917,8512873,8536126,8622854,8736523,8739148,8765401,8773872,8784182,9136109,9139625,9164407,9423055,9427171,9437297,9448973,9469890,9535215,9573623,9642814,9709967,9759522,9968218];
reader_token=[4,876808,60920,453,5780,2328608,18,200,8,8028,8756,85,6,3513708,69670,220694,8080498,103675,5118930,854097,52152,1860,1140,24496,143,2309380,173889,200,5,8,62,2928,8,40,1734876,588928,1748313,79162,584,9600,1,68,6,580,1124132,99580,1072,4125,6,725,42,87,1456,40860,5083052,211008,8012,50,103260,56,880,9589887,5438,139613,1,2414,706640,4848820,4263584,1,64,82056,71620,9901,17544,1246126,1,172,12,5480061,176424,680724,1351140,57860,2,60880,356,2,3664280,112,387,84,902,170910,9659392,4332,7206375,775,7973824,326344,91236,16,7,12,34,32,67404,4335232,4,30870,1,11484,80,430,781136,2605,48992,958528,592,888,141180,95560,281780,1250,1,755,46986,192260,4,488920,24,1,10064,190,872,8434544,8088,4598,308,63772,5921190,642122,7042236,876532,9979733,935,6915,1104,2,1,2526,23012,439,44788,624880,2,3724,970,526391,8,8,9948,1100,7938,456,57610,6858,1519,1,1618,176,50,1747564,1,4034344,5,765610,78020,33546,7609,1,5400,3,313805,1,648,5312,2171130,298920,10,84,65972,8128793,1,96517,89389,1,13788,101116,6,853385,973304,94,32540,8,451803,1460398,1781667,46922,132,52274,336,6909355,40583,11,50,2219968,440,1002576,936424,86,448,92002,876,1,36,200,395920,85475,7,8320,397004,21850,554,860,76,28,15,7314,1739367,85112,1674,7177380,2,100,9,53,3480,224,11961,695,583,8870,8230,8,6828607,567738,75,3,264,659,46,2265,6231080,9911760,32,3444128,25,4385,500,2371,48482,55752,2,6172,6427708,95,967050,609883,1,781803,100,8725,81,440,431582,15782,1516,904,980772,80,785,3226436,85,639269,60,75760,8194375,95,167735,9721420,27109,5662,7758,1520,121230,8054109,7024,330880,2658180,944,11679,1856412,464,3112876,24,11,776,5405,5338,8878256,39232,1480,7750,4637,5177199,7528,86736,28011,12,90,827,16,394032,1007002,3836,180,870631,6332850,77,255,648,74,1267002,659,27,8280,92,2030,7,6392,7834,3563963,2819,643670,4439,954756,8259812,16,252685,76,1258020,62,96,19921,365206,772,8,7,8862,4976000,6,442,134796,710,19468,4000,239,64072,6,5337762,7648,9260,45795,576812,578674,124,38,772,6,851607,7026661,7264,86200,72158,57170,1,1522925,8365208,6639570,28,19906,5,870,928,27,1672,30,1871722,1746416,8300,267,1,19,1750,70072,12,133,140,1556,41063,84,29574,556726,8,62400,154450,1,8189,2395952,1552100,784496,2,556,1112288,8133996,4734,907700,105,193760,46,1482760,10,600,318,584,4558832,23990,275000,1736,7003991,1843632,7389,18595,2395,94976,100,4992710,4,711125,38448,19,453,99248,4056,5677,467260,337230,62,4669482,6,327993,70452,3,9170,882792,32,7743451,96,1100,177910,264,11626,154154,50,7108960,5510,40,54,9415,7311,484,163278,77064,847,1399650,11,250,544,1,2429213,654096,68,32,2,5131844,8,2185960,968749,313727,4,149025,18,5702325,113962,2785828,699570,802370,68,7263175,56235,808769,3,241,8012,267360,8365949,250995,58,938,6,487030,608018,9899400,1,51642,4936180,4405,33,94,7030,88,8099744,5076952,200,3,88640,4421677,50425,23163,3725225,9780,8792,14424,78250,5,8,338912,71875,150515,75,1984,9654,86,1,8002288,283900,296,92,74,5931250,91,218630,153630,1866857,12020,767,8,4,751,12,7219,52328,5420,5,5699591,110,640,4,389970,4648,2,92,4992,3294166,33884,811998,45315,997,232785,7,489110,690,2028,67412,2471,6564,12861,151,2458,100,2,358440,908,7368,95234,3,557040,41642,7325,570,488450,58,172,7608596,378825,9212,6692376,6,21060,255768,163,68000,912008,437,17736,72363,489,660,170,85153,19,916,77296,6205926,1,960,6972,1600,764750,5136,60,2,9,8,494914,180,35616,800,2992,82,5,530,4712,624,1634350,703876,25,6,3780004,4196920,85996,616,1,8,8137725,7942170,3046772,4,5546349,300,1620838,18,2503552,10,6,6024,10,569645,6,34099,46422,4,229568,737,436173,3190,1,16719,6,7716431,56000,63736,220,2172,9262336,2725556,99032,20,155,1207,86818,5620,3,62,153164,8861780,192,200,110362,838768,72972,56,1860,923126,532,195126,61807,8127891,708,74,186976,3749720,6362577,565424,924,20,64,245576,3206,2154388,44,240,860,1280256,438756,17,5920330,8686396,4278,46,45,972500,140,57,49704,6795750,9012,120,76424,33000,84912,49496,5028742,2085986,11420,9840860,6,2828550,881622,1,322,8660,14312,5169936,3746188,9722,2450,118,2901,4838,8,9158734,2094591,164,9,9637280,117,13908,6012792,3272,6820,80,1,7607181,400,28,1256,97336,96147,58,2,5760,4409,17620,2923358,80,984,1574952,480,27552,12,5770,506,87,182144,76770,4975,1375,8221266,1497642,2976,16000,2579,80,99424,83633,5380818,328,10,11365,532250,69906,602958,70,12,6220416,54738,1,88,4904,320,196,12295,3285976,2,63,620,689,4260218,1,899872,8800,6,1,1994,5580,1956240,1,10,3840,24,1,48969,155,98,36557,5086322,10,84,10,1068296,1413844,277,31035,50960,467874,4,58868,16,5530625,852,376,1424,307,432987,2,31,16,6,2972,40,8020,1955,4935,121437,158692,58496,904276,670,5404965,4,7380,433704,3908557,5795307,1,16,856,1,8800,1,696,700,76930,3092,5612,781590,639680,4914,8,349,510856,1247942,484547,150,70,9413,501760,3589,4,85721,367934,288,175,68,55220,1368708,65660,37,13640,1,570,155280,6822,3,2842,30,80,136,3717,72412,12944,401312,868,1,53284,8653992,760,14751,7,55161,2520825,824160,72,45739,50000,8276544,77517,1113911,3,8893,38560,6324,8276210,3224250,51040,2510,165136,6438,1,77,9770625,277728,14,48,768904,6867,3,7141760,949440,750,5758,97710,7647979,11976,1,858764,56,346];
reader_bit=[1,6,5,3,4,7,2,3,1,4,4,2,1,7,5,6,7,6,7,6,5,4,4,5,3,7,6,3,1,1,2,4,1,2,7,6,7,5,3,4,1,2,1,3,7,5,4,4,1,3,2,2,4,5,7,6,4,2,6,2,3,7,4,6,1,4,6,7,7,1,2,5,5,4,5,7,1,3,2,7,6,6,7,5,1,5,3,1,7,3,3,2,3,6,7,4,7,3,7,6,5,2,1,2,2,2,5,7,1,5,1,5,2,3,6,4,5,6,3,3,6,5,6,4,1,3,5,6,1,6,2,1,5,3,3,7,4,4,3,5,7,6,7,6,7,3,4,4,1,1,4,5,3,5,6,1,4,3,6,1,1,4,4,4,3,5,4,4,1,4,3,2,7,1,7,1,6,5,5,4,1,4,1,6,1,3,4,7,6,2,2,5,7,1,5,5,1,5,6,1,6,6,2,5,1,6,7,7,5,3,5,3,7,5,2,2,7,3,7,6,2,3,5,3,1,2,3,6,5,1,4,6,5,3,3,2,2,2,4,7,5,4,7,1,3,1,2,4,3,5,3,3,4,4,1,7,6,2,1,3,3,2,4,7,7,2,7,2,4,3,4,5,5,1,4,7,2,6,6,1,6,3,4,2,3,6,5,4,3,6,2,3,7,2,6,2,5,7,2,6,7,5,4,4,4,6,7,4,6,7,3,5,7,3,7,2,2,3,4,4,7,5,4,4,4,7,4,5,5,2,2,3,2,6,7,4,3,6,7,2,3,3,2,7,3,2,4,2,4,1,4,4,7,4,6,4,6,7,2,6,2,7,2,2,5,6,3,1,1,4,7,1,3,6,3,5,4,3,5,1,7,4,4,5,6,6,3,2,3,1,6,7,4,5,5,5,1,7,7,7,2,5,1,3,3,2,4,2,7,7,4,3,1,2,4,5,2,3,3,4,5,2,5,6,1,5,6,1,4,7,7,6,1,3,7,7,4,6,3,6,2,7,2,3,3,3,7,5,6,4,7,7,4,5,4,5,3,7,1,6,5,2,3,5,4,4,6,6,2,7,1,6,5,1,4,6,2,7,2,4,6,3,5,6,2,7,4,2,2,4,4,3,6,5,3,7,2,3,3,1,7,6,2,2,1,7,1,7,6,6,1,6,2,7,6,7,6,6,2,7,5,6,1,3,4,6,7,6,2,3,1,6,6,7,1,5,7,4,2,2,4,2,7,7,3,1,5,7,5,5,7,4,4,5,5,1,1,6,5,6,2,4,4,2,1,7,6,3,2,2,7,2,6,6,7,5,3,1,1,3,2,4,5,4,1,7,3,3,1,6,4,1,2,4,7,5,6,5,3,6,1,6,3,4,5,4,4,5,3,4,3,1,6,3,4,5,1,6,5,4,3,6,2,3,7,6,4,7,1,5,6,3,5,6,3,5,5,3,3,3,5,2,3,5,7,1,3,4,4,6,4,2,1,1,1,6,3,5,3,4,2,1,3,4,3,7,6,2,1,7,7,5,3,1,1,7,7,7,1,7,3,7,2,7,2,1,4,2,6,1,5,5,1,6,3,6,4,1,5,1,7,5,5,3,4,7,7,5,2,3,4,5,4,1,2,6,7,3,3,6,6,5,2,4,6,3,6,5,7,3,2,6,7,7,6,3,2,2,6,4,7,2,3,3,7,6,2,7,7,4,2,2,6,3,2,5,7,4,3,5,5,5,5,7,7,5,7,1,7,6,1,3,4,5,7,7,4,4,3,4,4,1,7,7,3,1,7,3,5,7,4,4,2,1,7,3,2,4,5,5,2,1,4,4,5,7,2,3,7,3,5,2,4,3,2,6,5,4,4,7,7,4,5,4,2,5,5,7,3,2,5,6,5,6,2,2,7,5,1,2,4,3,3,5,7,1,2,3,3,7,1,6,4,1,1,4,4,7,1,2,4,2,1,5,3,2,5,7,2,2,2,7,7,3,5,5,6,1,5,2,7,3,3,4,3,6,1,2,2,1,4,2,4,4,4,6,6,5,6,3,7,1,4,6,7,7,1,2,3,1,4,1,3,3,5,4,4,6,6,4,1,3,6,7,6,3,2,4,6,4,1,5,6,3,3,2,5,7,5,2,5,1,3,6,4,1,4,2,2,3,4,5,5,6,3,1,5,7,3,5,1,5,7,6,2,5,5,7,5,7,1,4,5,4,7,7,5,4,6,4,1,2,7,6,2,2,6,4,1,7,6,3,4,5,7,5,1,6,2,3];